package com.mlh.dp.基础题目;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/4/18 10:40
 * @DESCRIPTION
 */
// 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
public class 不同的二叉搜索树 {
    //代码自己写出，一开始自己想有一些思路，但是比较乱，看了代码随想录后理清思路，自己写出代码
    //这题的关键是找到了重叠子问题
    //n个节点，以第一个元素为根节点,此时所有的节点都必须在该节点的右子树上（因为都比他大），
    // 那么这些剩下的节点有几种排法呢?  不就是n-1个节点的排法，它排完直接把头结点接上去就可以
    //同理尾结点也可以这么做
    //接下来就到了中间节点了，中间节点的位置就划分了左子树有几个节点，
    // 右子树有几个节点，左子树排法数量*右子树排法数量=该中间节点为头结点的排法数量
    //将所有的中间节点循环处理，就能得到最终的答案
    public int numTrees(int n) {
        if(n<2){
            return 1;
        }
        int []res=new int[n+1];
        res[1]=1;
        res[2]=2;
        for (int i = 3; i <= n; i++) {
            res[i]=2*res[i-1];
            for (int j = 1; j < i-1; j++) {
                res[i]+=res[j]*res[i-1-j];
            }
        }
        return res[n];
    }

    public int practice(int n) {
        if(n<=2){
            return n;
        }
        int[]dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for (int i = 2; i <=n; i++) {
            for (int j = 1; j <=i; j++) { //以1,2,3....i每个节点为根节点，进行构造树，然后累计和
                //dp[j-1]是拥有j-1个节点作为左子树的种类数，
                //dp[i-j]]是拥有i-j]个节点作为右子树的种类数，拼接上根节点就是一种树
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
